package com.gxc.linkedList;

/**
 * 单向环形链表--约瑟夫问题
 *
 * 设编号为1，2，3...，n个人围坐一圈，约定编号为k(1<=k <= n)的人从1开始报数，
 * 数到m的那个人出列，紧接着他的下一位又从1开始报数，数到m的那个人又出列，
 * 以此类推，直到所有人出列为止，由此产出一个编号的序列
 */
public class JosephusKill {

    public ListNode handle(ListNode head, int m) {
        if (head == null || head.next == null) return head;

        //确定链表的最后一个节点
        ListNode last = head.next;
        while (last.next != head) {
            last = last.next;
        }

        int count = 0;
        while (last != head) {
            if (++count == m) {
                last.next = head.next;
                //重新报数
                count = 0;
            } else {
                last = last.next;
            }//重新链表的头和尾
            head = last.next;
        }
        return last;
    }

    /**
     * 递归解法
     * 新环编号=（旧环编号-k)%旧总人数 得到的，所以旧环编号可以通过逆推得到：旧环编号=（新环编号+k)%旧总人数
     * f(n,m) = (f(n-1, m) + m)%n
     * @param head
     * @param m
     * @return
     */
    public ListNode recursion(ListNode head, int m) {
        //计算循环链表长度
        int l = 0;
        ListNode node = head;
        while (node.next != head) {
            l++;
            node = node.next;
        }

        if (l ==1) return head;
        int res = f(l, m);
        //原来的编号从1  先编号重新排序，所以+1 才是实际的编号
        res++;
        //因为初始编号是1，所以先--
        while (--res!=0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    private int f(int n, int m) {
        if (n == 1) return 0;
        return (f(n-1, m) + m)%n;
    }

    public ListNode iteration(ListNode head, int m) {
        //计算循环链表长度
        int l = 0;
        ListNode node = head;
        while (node.next != head) {
            l++;
            node = node.next;
        }

        if (l ==1) return head;
        int res = f2(l, m);
        //原来的编号从1  先编号重新排序，所以+1 才是实际的编号
        res++;
        //因为初始编号是1，所以先--
        while (--res!=0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    /**
     * 旧环编号=（新环编号+k)%旧总人数
     * @param n
     * @param m
     * @return
     */
    private int f2(int n, int m) {
        int value = 0;
        for (int i = 2; i <= n; i++) {
            value = (value + m)%i;
        }
        return value;
    }


    public static class ListNode {
        int val;
        JosephusKill.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, JosephusKill.ListNode next) { this.val = val; this.next = next; }
    }
}
